package com.algorithm.ch1.cjm.string;

/**
 * 数数并说
 * 报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
 * <p>
 * 1.     1
 * 2.     11
 * 3.     21
 * 4.     1211
 * 5.     111221
 * 1 被读作  "one 1"  ("一个一") , 即 11。
 * 11 被读作 "two 1s" ("两个一"）, 即 21。
 * 21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。
 * <p>
 * 给定一个正整数 n ，输出报数序列的第 n 项。
 * <p>
 * 注意：整数顺序将表示为一个字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1
 * 输出: "1"
 * 示例 2:
 * <p>
 * 输入: 4
 * 输出: "1211"
 */
public class CountAndSay {


    /**
     * T(n) = n^2
     * f(n) = n^2
     * 时间复杂度求法不确定？
     * @param n
     * @return
     */
    public String countAndSay(int n) {

        if(n < 1){
            return null;
        }

        String res = null;

        for(int i = 0; i < n ; i++){

            res = say(res);
        }

        return res;
    }

    //把1211 变化为  111221
    public String say(String say){

        if(say == null){
            return "1";
        }

        StringBuffer sb = new StringBuffer();

        for(int i = 0; i < say.length(); i ++){

            int ch = say.charAt(i) - '0';
            int count = 1;

            int j = i + 1;
            while (j < say.length() && say.charAt(j) == say.charAt(i)){
                count ++;
                j++;
                i++;
            }
            sb.append(count).append(ch);

        }
        return sb.toString();
    }

    public static void main(String[] args) {

        System.out.println(new CountAndSay().say("0"));
    }


}
